package leetcode_classic150;

import model.ListNode;
import model.Node;
import model.TreeNode;

import java.util.*;


class Interval {
    int start;
    int end;

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}


public class Demo1 {

    // 57. 插入区间
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();

        int i = 0, n = intervals.length;
        // 1. 添加前置区间
        for(; i < n; i++) {
            if(newInterval[0] > intervals[i][1]) list.add(intervals[i]);
            else break;
        }
        // 进行特判，若插入区间比所有区间都大，则扩大数组后插入 newInterval
        if(i == n) {
            intervals = Arrays.copyOf(intervals, n + 1);
            intervals[n] = newInterval;
            return intervals;
        }

        // 2. 添加插入区间
        // 确定区间起点的大小
        int start = Math.min(newInterval[0], intervals[i][0]);
        // 寻找区间终点所在的区间
        while(i < n && newInterval[1] >= intervals[i][0]) i++;
        i--;
        // 确定区间终点的大小
        int end = i >= 0 ? Math.max(newInterval[1], intervals[i][1]) : newInterval[1];      // 判断插入区间是否比所有的区间小
        list.add(new int[]{start, end});

        // 3. 添加后续区间
        while(++i < n) list.add(intervals[i]);

        int[][] res = new int[list.size()][2];
        for(int j = 0; j < list.size(); j++) {
            res[j] = list.get(j);
        }
        return res;
    }



    // BM89 合并区间
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        ArrayList<Interval> ret = new ArrayList<>();
        if(intervals.size() == 0) return ret;
        Collections.sort(intervals, (o1, o2) -> o1.start - o2.start);

        for(int i = 0; i < intervals.size(); ) {
            int start = intervals.get(i).start, end = intervals.get(i).end;
            while(i < intervals.size() && end >= intervals.get(i).start) {
                // end 应该取较大值
                end = Math.max(end, intervals.get(i++).end);
            }
            ret.add(new Interval(start, end));
        }
        return ret;
    }


    // 120. 三角形最小路径和
    public int minimumTotal(List<List<Integer>> triangle) {
        // dp[i][j]: 由[0,0] 到达 [i,j] 所有路径中的最小路径和
        int n = triangle.size();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for(int i = 1; i <= n; i++) {
            for(int j = i; j >= 1; j--) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + triangle.get(i - 1).get(j - 1);
            }
            if(i == 1) dp[0] = Integer.MAX_VALUE;
        }

        int res = Integer.MAX_VALUE;
        for(int x : dp) res = Math.min(res, x);
        return res;
    }


    // 92. 反转链表 II
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode prev = newHead, cur =head;

        for(int sz = left - 1; sz > 0; sz--) {
            prev = cur;
            cur = cur.next;
        }

        // 反转链表
        ListNode tmp = null;
        for(int sz = right - left + 1; sz > 0; sz--) {
            ListNode next = cur.next;
            cur.next = tmp;
            tmp = cur;
            cur = next;
        }
        prev.next.next = cur;
        prev.next = tmp;
        return newHead.next;
    }



    // 150. 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();

        for(String arr : tokens) {
            char c = arr.charAt(0);
            // 提取操作数
            if((c >= '0' && c <= '9' ) || c == '-' && arr.length() > 1) {
                stack.push(Integer.valueOf(arr));
            } else {
                int num2 = stack.pop(), num1 = stack.pop();
                stack.push(calculate(num1, num2, c));
            }
        }
        return stack.pop();
    }
    private int calculate(int num1, int num2, char op) {
        if (op == '+') return num1 + num2;
        else if(op == '-') return num1 - num2;
        else if(op == '*') return num1 * num2;
        return num1 / num2;
    }



    // 117. 填充每个节点的下一个右侧节点指针 II
    public Node connect(Node root) {
        if (root == null) return null;

        root.next = null;
        Node head = root;
        while (head != null) {
            Node newHead = new Node();
            Node newTail = newHead;
            while (head != null) {
                if (head.left != null) {
                    newTail.next = head.left;
                    newTail = newTail.next;
                }
                if (head.right != null) {
                    newTail.next = head.right;
                    newTail = newTail.next;
                }
                head = head.next;
            }
            head = newHead.next;
            newTail.next = null;
        }
        return root;
    }


    // 45. 跳跃游戏 II
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        int cur = 0, right = 0, step = 0;

        while (right < n) {
            int nextRight = right;
            while (cur <= right) {
                if (cur + nums[cur] > nextRight) nextRight = nums[cur] + cur;
                cur++;
            }
            right = nextRight;
            step++;
            if(right >= n - 1) return step;
        }
        return step;
    }

    // 55. 跳跃游戏
    public boolean canJump(int[] nums) {
        int cur = 0, right = nums[0], n = nums.length;

        for (; cur <= right; cur++) {
            if (cur + nums[cur] > right) right = cur + nums[cur];
            if (right >= n - 1) return true;
        }
        return false;
    }



    // 122. 买卖股票的最佳时机 II
    public int maxProfit2(int[] prices) {
        // 方法一: 动态规划解法
        // f[i]: 第 i 天结束后持有股票所获得的最大利润
        // g[i]: 第 i 天结束后未持有股票所获得的最大利润
        int n = prices.length;
        int[] f = new int[n], g = new int[n];
        f[0] = -prices[0];

        for(int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = Math.max(f[ i - 1] + prices[i], g[i - 1]);
        }
        return g[n - 1];
    }



    // 121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int res = 0, min = Integer.MAX_VALUE;
        for(int x : prices) {
            if(x <= min) min = x;
            else res = Math.max(res, x - min);
        }
        return res;
    }


    // 189. 轮转数组
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        if (k == 0) return;

        int[] arr = new int[k];
        for (int i = 0; i < k; i++) arr[i] = nums[n - k + i];
        for (int i = n - 1, count = n - k; count-- > 0; i--) nums[i] = nums[i - k];
        for (int i = 0; i < k; i++) nums[i] = arr[i];
    }



    // 169. 多数元素
    public int majorityElement(int[] nums) {
        // 方法一: 对数组进行排序，nums[n / 2] 即为多数元素

        // 方法二: 摩尔投票法
        int res = nums[0], count = 1;
        for (int x : nums) {
            if (count == 0) {
                res = x;
                count = 1;
            } else {
                if (x == res) count++;
                else count--;
            }
        }
        return res;
    }



    // 80. 删除有序数组中的重复项 II
    public int removeDuplicates2(int[] nums) {
        int n = nums.length, res = 0;
        for (int i = 0, j = 0; i < n; ) {
            // 此时 j 下标的元素为重复元素的下一个
            while (j < n && nums[j] == nums[i]) j++;
            nums[res++] = nums[j - 1];
            if (j - i >= 2) {
                nums[res++] = nums[j - 1];
            }
            i = j;
        }
        return res;
    }


    // 26. 删除有序数组中的重复项
    public int removeDuplicates(int[] nums) {
        // k 表示所有非重复数组中最后一个元素的下标 + 1
        int n = nums.length, k = 0;
        for(int i = 0, j = 0; i < nums.length; ) {
            while (i < n - 1 && nums[i] == nums[i + 1]) i++;
            nums[k++] = nums[i++];
        }
        return k;
    }


    // 27. 移除元素
    public int removeElement(int[] nums, int val) {
        // res 表示所有值为 val 的元素在数组的第一个下标
        int cur = 0, res = nums.length, n = nums.length;
        while (cur < res) {
            if (nums[cur] != val) cur++;
            else {
                // 交换 res - 1 与 cur的元素
                int tmp = nums[cur];
                nums[cur] = nums[--res];
                nums[res] = tmp;
            }
        }
        return res;
    }


    // 303. 区域和检索 - 数组不可变
    class NumArray {
        // 前缀和:memo[i]表示 0 ~ i区间所有数字之和
        int[] memo;

        public NumArray(int[] nums) {
            int n = nums.length;
            memo = new int[n + 1];
            for(int i = 1; i <= n; i++) {
                memo[i] = memo[i - 1] + nums[i - 1];
            }
        }

        public int sumRange(int left, int right) {
            return memo[right + 1] - memo[left];
        }
    }



    // 13. 罗马数字转整数
    public int romanToInt(String s) {
        String[] str1 = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] str2 = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

        int res = 0;
        for (int i = 0, j = 0; i < s.length(); ) {
            // 代表找到了对应的罗马数字,且罗马数字第一个字符的下标必须 == i
            if (s.indexOf(str1[j], i) == i) {
                res += str2[j];
                i += str1[j].length();
            } else {
                j++;
            }
        }
        return res;
    }


    // 1261. 在受污染的二叉树中查找元素
    class FindElements {
        Set<Integer> set;

        public FindElements(TreeNode root) {
            set = new HashSet<>();
            set.add(0);
            dfs(root.left, 1);
            dfs(root.right, 2);
        }

        public boolean find(int target) {
            return set.contains(target);
        }

        private void dfs(TreeNode root, int val) {
            if(root == null) return;
            set.add(val);
            dfs(root.left, val * 2 + 1);
            dfs(root.right, val * 2 + 2);
        }
    }




}
